{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"../../img/ods_stickers.jpg\">\n",
    "## Открытый курс по машинному обучению. Сессия № 2\n",
    "Автор материала: программист-исследователь Mail.ru Group, старший преподаватель Факультета Компьютерных Наук ВШЭ Юрий Кашницкий. Материал распространяется на условиях лицензии [Creative Commons CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/). Можно использовать в любых целях (редактировать, поправлять и брать за основу), кроме коммерческих, но с обязательным упоминанием автора материала."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center>Тема 10. Бустинг\n",
    "## <center>Часть 2. Сравнение Xgboost и градиентного бустинга Sklearn</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## XGBoost\n",
    "\n",
    "Выделяют три группы параметров:\n",
    "- Общие параметры, отвечающие за базовый алгоритм для бустинга и распараллеливание.\n",
    "- Параметры выбранного базового алгоритма.\n",
    "- Параметры обучения, отвечающие за функцию потерь и метрику качества на валидации.\n",
    "\n",
    "**1. Общие параметры:**\n",
    "- booster [default=gbtree] - тип базового алгоритма для бустинга: дерево решений gbtree или линейная модель gblinear. \n",
    "- silent [default=0] - выдавать (silent=0) или нет (silent=1) сообщения по ходу работы алгоритма.\n",
    "- nthread [default to maximum number of threads available if not set] - число нитей доступных для параллельной работы xgboost.\n",
    "\n",
    "**2. Параметры базового алгоритма:**\n",
    "\n",
    "**2.1. Дерево решений:**\n",
    "- eta [default=0.3] - темп обучения, перед добавлением дерева в композицию оно умножается на eta. Используется для предотвращения переобучения за счёт \"сокращения\" весов базовых алгоритмов, делая модель более консервативной. Чем меньше eta, тем больше нужно итераций num_boost_round для обучения модели с хорошим качеством. Диапазон: [0, 1]\n",
    "- gamma [default=0] - минимальное снижение значения функции потерь, необходимое для дальнейшего разбиения вершины дерева. Большие значения gamma > 0 приводят к более консервативным моделям. Диапазон: [0, $\\infty$).\n",
    "- max_depth [default=6] - максимальная глубина дерева. Диапазон: [1, $\\infty$). \n",
    "- min_child_weight [default=1] - минимальное необходимое (взвешенное) число примеров в каждой вершине. Чем больше, тем более консервативна итоговая модель. Диапазон: [0, $\\infty$).\n",
    "- max_delta_step [default=0] - обычно равен нулю. Положительные значения используются при несбалансированных классах для ускорения сходимости. Диапазон [0, $\\infty$).\n",
    "- subsample [default=1] - доля выборки, используемая для обучения каждого дерева. Если subsample < 1, то выбирается случайная подвыборка, что помогает в борьбе с переобучением. Диапазон: (0, 1]\n",
    "- colsample_bytree [default=1] - доля признаков, используемая для обучения каждого дерева. Диапазон: (0, 1]\n",
    "- lambda [default=1] - коэффициент перед $L_2$-регуляризатором в функции потерь.\n",
    "- alpha [default=0] - коэффициент перед $L_1$-регуляризатором в функции потерь.\n",
    "\n",
    "**2.2. Линейная модель:**\n",
    "- lambda [default=0] - коэффициент перед $L_2$-регуляризатором вектора весов в функции потерь.\n",
    "- alpha [default=0] - коэффициент перед $L_1$-регуляризатором вектора весов в функции потерь.\n",
    "- lambda_bias [default=0] - коэффициент перед $L_2$-регуляризатором смещения (свободного члена) в функции потерь.\n",
    "\n",
    "**3. Параметры задачи обучения:**\n",
    "- objective [default=reg:linear] - используемая при обучении функция потерь:\n",
    "    - \"reg:linear\" – линейная регрессия.\n",
    "    - \"reg:logistic\" – логистическая регрессия.\n",
    "    - \"binary:logistic\" – логистическая регрессия для бинарной классификации, на выходе - вероятность.\n",
    "    - \"binary:logitraw\" – то же самое, но на выходе - значение до его преобразования логистической функцией.\n",
    "    - \"count:poisson\" – регрессия Пуассона (используется для оценки числа каких-то событий, счётный признак), на выходе - матожидания распределения Пуассона. В этом случае max_delta_step автоматически устанавливается равным 0.7.\n",
    "    - \"multi:softmax\" – обобщение логистической регрессии на многоклассовый случай. При этом нужно задать параметр num_class.\n",
    "    - \"multi:softprob\" – то же самое, но на выходе - вектор размера ndata * nclass, который можно преобразовать в матрицу, содержащую вероятности отнесения данного объекта к данному классу.\n",
    "    - \"rank:pairwise\" – используется для задач ранжирования.\n",
    "- base_score [default=0.5] - инициализация значения модели для всех примеров, глобальное смещение.\n",
    "- eval_metric [default according to objective] - метрика качества на валидационной выборке (по умолчанию соответствует функции потерь: rmse - для регрессии, error - для классификации, mean average precision - для ранжирования). Выбрать можно одну из следующих метрик:\n",
    "    - \"rmse\": root mean square error.\n",
    "    - \"logloss\": минус логарифм правдоподобия.\n",
    "    - \"error\": доля ошибок для бинарной классификации.\n",
    "    - \"merror\": то же самое для многоклассовой классификации.\n",
    "    - \"mlogloss\": logloss для многоклассовой классификации.\n",
    "    - \"auc\": AUC.\n",
    "    - \"ndcg\": Normalized Discounted Cumulative Gain.\n",
    "    - \"map\": Mean average precision.\n",
    "    - \"ndcg@n\",”map@n”: здесь n - целое число, первые n позиций в списке не учитываются.\n",
    "    - \"ndcg-\",”map-”,”ndcg@n-”,”map@n-”: списку из всех положительных примеров будет присвоено значение 0 (вместо 1).\n",
    "- seed [default=0] - для воспроизводимости \"случайности\".\n",
    "\n",
    "**Параметры в xgboost.train**:\n",
    "- params (dict) – параметры, описанные выше.\n",
    "- dtrain (DMatrix) – обучающая выборка.\n",
    "- num_boost_round (int) – число итераций бустинга.\n",
    "- evals (list) – список для оценки качества во время обучения.\n",
    "- obj (function) – собственная функция потерь.\n",
    "- feval (function) – собственная функция для оценки качества.\n",
    "- maximize (bool) – нужно ли максимизировать feval.\n",
    "- early_stopping_rounds (int) – активирует early stopping. Ошибка на валидации должна уменьшаться каждые early_stopping_rounds итераций для продолжения обучения. Список evals должен быть не пуст. Возвращается модель с последней итерации. Если произошел ранний останов, то модель будет содержать поля: bst.best_score и bst.best_iteration.\n",
    "- evals_result (dict) – результаты оценки качества.\n",
    "- verbose_eval (bool) – вывод значения метрики качества на каждой итерации бустинга.\n",
    "- learning_rates (list or function) – коэффициент скорости обучения для каждой итерации - list l: eta = l[boosting round] - function f: eta = f(boosting round, num_boost_round).\n",
    "- xgb_model (file name of stored xgb model or ‘Booster’ instance) – возможность продолжить обучения имеющейся модели XGB.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## sklearn.ensemble.GradientBoostingClassifier\n",
    "- loss [default=\"deviance\"] - оптимизируемая функция потерь.  Одна из {\"deviance\", \"exponential\"}. Первая соответствует логистической регрессии и возвращает вероятности, вторая - AdaBoost.\n",
    "- learning_rate [default=0.1] - темп обучения, аналогично eta для XGBoost.\n",
    "- n_estimators [default=100] - число итераций градиентного бустинга.\n",
    "- max_depth [default=3] - аналогично max_depth для XGBoost.\n",
    "- min_samples_split [default=2] - минимальное число примеров, необходимое для разветвления в данной вершине,  аналогично min_child_weight для XGBoost.\n",
    "- min_samples_leaf [default=1] - минимальное число примеров в листе.\n",
    "- min_weight_fraction_leaf [default=0.0] - минимальное взвешенное число примеров в листе.\n",
    "- subsample [default=1.0] - аналогично subsample для XGBoost.\n",
    "- max_features (int, float, string or None) [default=None] - число (или доля) признаков, используемых при разбиении вершины.\n",
    "    - \"auto\", тогда max_features=sqrt(n_features).\n",
    "    - \"sqrt\", тогда max_features=sqrt(n_features).\n",
    "    - \"log2\", тогда max_features=log2(n_features).\n",
    "    - None, тогда max_features=n_features.\n",
    "- max_leaf_nodes [default=None]\n",
    "- init (BaseEstimator or None) [default=None] - алгоритм для начальных предсказаний.\n",
    "- verbose [default=0] - аналогично silent для XGBoost.\n",
    "- warm_start [default=False] - если True, используется ансамбль с предыдущего вызова fit, новые алгоритмы добавляются к нему, иначе строится новый алгоритм."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Сравнение алгоритмов по времени работы\n",
    "\n",
    "Посмотрим на время обучения классификаторов XGBooster и GradientBoostingClassifier. Для этого будем генерировать выборку из 1000 объектов и 50 признаков с помощью sklearn.datasets.make_classification и замерять время обучения."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "import xgboost as xgb\n",
    "from sklearn.datasets import make_classification\n",
    "from sklearn.ensemble import GradientBoostingClassifier\n",
    "from tqdm import tqdm_notebook\n",
    "\n",
    "xgb_params1 = {\n",
    "    \"booster\": \"gbtree\",\n",
    "    \"max_depth\": 3,\n",
    "    \"eta\": 0.1,\n",
    "    \"silent\": 1,\n",
    "    \"objective\": \"binary:logistic\",\n",
    "    \"nthread\": 1,\n",
    "}\n",
    "xgb_params2 = {\n",
    "    \"booster\": \"gbtree\",\n",
    "    \"max_depth\": 3,\n",
    "    \"eta\": 0.1,\n",
    "    \"silent\": 1,\n",
    "    \"objective\": \"binary:logistic\",\n",
    "    \"nthread\": 4,\n",
    "}\n",
    "sklearn_params = {\"n_estimators\": 100, \"max_depth\": 3}\n",
    "\n",
    "xgb_time1 = list()\n",
    "xgb_time2 = list()\n",
    "sklearn_time = list()\n",
    "\n",
    "n_runs = 50\n",
    "\n",
    "for i in tqdm_notebook(range(n_runs)):\n",
    "    # Generating dataset\n",
    "    X, y = make_classification(n_samples=1000, n_features=50, n_informative=20)\n",
    "    # Training XGBooster (nthread=1)\n",
    "    t = time.time()\n",
    "    bst = xgb.train(xgb_params1, xgb.DMatrix(X, label=y), num_boost_round=100)\n",
    "    elapsed = time.time() - t\n",
    "    xgb_time1.append(elapsed)\n",
    "    # Training XGBooster (nthread=4)\n",
    "    t = time.time()\n",
    "    bst = xgb.train(xgb_params2, xgb.DMatrix(X, label=y), num_boost_round=100)\n",
    "    elapsed = time.time() - t\n",
    "    xgb_time2.append(elapsed)\n",
    "    # Training GradientBoostingClassifier\n",
    "    t = time.time()\n",
    "    clf = GradientBoostingClassifier(**sklearn_params).fit(X, y)\n",
    "    elapsed = time.time() - t\n",
    "    sklearn_time.append(elapsed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib  inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "xgb_mean1 = sum(xgb_time1) / n_runs\n",
    "xgb_mean2 = sum(xgb_time2) / n_runs\n",
    "sklearn_mean = sum(sklearn_time) / n_runs\n",
    "\n",
    "plt.figure(figsize=(12, 8))\n",
    "plt.plot(xgb_time1, label=\"XGBooster (nthread = 1)\", lw=2)\n",
    "plt.plot(xgb_time2, label=\"XGBooster (nthread = 4)\", lw=2)\n",
    "plt.plot(sklearn_time, label=\"GradientBoostingClassifier\", lw=2)\n",
    "plt.legend(loc=\"best\")\n",
    "plt.text(\n",
    "    1,\n",
    "    (xgb_mean1 + sklearn_mean) / 2,\n",
    "    \"XGBoost (nthread = 1) mean time = %.2f\" % xgb_mean1\n",
    "    + \"\\n\\nXGBoost (nthread = 4) mean time = %.2f\" % xgb_mean2\n",
    "    + \"\\n\\nScikit-learn mean time = %.2f\" % sklearn_mean,\n",
    "    fontsize=15,\n",
    ")\n",
    "plt.xlabel(\"Iteration number\")\n",
    "plt.ylabel(\"Running time, sec\")\n",
    "plt.title(\"XGBoost vs. GradientBoostingClassifier comparison\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Выводы\n",
    "\n",
    "Основные преимущества XGBoost по сравнению с sklearn.ensembles.GradientBoostingClassifier:\n",
    "- Помимо деревьев возможно использование линейных моделей в качестве базовых классификаторов.\n",
    "- Скорость работы.\n",
    "- Возможность распараллеливания.\n",
    "- Значительно больший выбор стандартных функций потерь, а также возможность задавать свою функцию потерь.\n",
    "- Наличие регуляризаторов в итоговой функции потерь и возможность задавать их коэффициенты, что даёт еще один метод борьбы с переобучением, помимо использования случайности (subsample, colsample_bytree) и основных параметров дерева решений.\n",
    "- Встроенная обработка missing values."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Полезные ссылки\n",
    "- [XGBoost](https://xgboost.readthedocs.org/en/latest/parameter.html)\n",
    "- [GradientBoostingClassifier](http://scikit-learn.org/stable/modules/generated/sklearn.ensemble.GradientBoostingClassifier.html)\n",
    "- [Сравнение](https://github.com/szilard/benchm-ml) различных библиотек для машинного обучения, в том числе sklearn и xgboost "
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  },
  "name": "2_1_7_regul.ipynb"
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
